/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/dungeon-game
   @Language: C++
   @Datetime: 19-12-02 15:25
   */

// Method 1, DFS+Memoried Search, Time 20ms, Space 14.8MB
class Solution {
	unordered_map<long,int> mem;
	int dfs(vector<vector<int> > &dungeon, int row, int col){
		if(row>=dungeon.size() || col>=dungeon[0].size()) return INT_MAX;
		const long key=(((long)row)<<32)|col;
		if(mem.count(key)) return mem[key];
		if(row+1==dungeon.size() && col+1==dungeon[0].size())
			return max(0,-dungeon[row][col]);
		int right=dfs(dungeon,row,col+1);
		int down=dfs(dungeon,row+1,col);
		int hp=max(0,min(right,down)-dungeon[row][col]);
		mem[key]=hp;
		return hp;
	}
public:
	int calculateMinimumHP(vector<vector<int>>& dungeon) {
		return dfs(dungeon,0,0)+1;
	}
};

// Method 2, DP, Time 12ms, Space 9.8MB
class Solution {
public:
	int calculateMinimumHP(vector<vector<int>>& dungeon) {
		if(dungeon.size()<1 || dungeon[0].size()<1) return -1;
		int m=dungeon.size(), n=dungeon[0].size();
		vector<vector<int> > dp(m,vector<int>(n,INT_MAX));
		dp[m-1][n-1]=max(0,-dungeon[m-1][n-1]);
		for(int i=m; i--;){
			for(int j=n; j--;){
				if(i==m-1 && j==n-1) continue;
				int right=j+1<n?dp[i][j+1]:INT_MAX;
				int down=i+1<m?dp[i+1][j]:INT_MAX;
				dp[i][j]=max(0,min(right,down)-dungeon[i][j]);
			}
		}
		return dp[0][0]+1;
	}
};

// Method 3, DP, Time 4ms, Space 9.5MB
class Solution {
public:
	int calculateMinimumHP(vector<vector<int>>& dungeon) {
		if(dungeon.size()<1 || dungeon[0].size()<1) return -1;
		int m=dungeon.size(), n=dungeon[0].size();
		vector<int> dp(n,INT_MAX);
		dp[n-1]=max(0,-dungeon[m-1][n-1]);
		for(int i=m; i--;){
			for(int j=n; j--;){
				if(i==m-1 && j==n-1) continue;
				int right=j+1<n?dp[j+1]:INT_MAX;
				dp[j]=max(0,min(right,dp[j])-dungeon[i][j]);
			}
		}
		return dp[0]+1;
	}
};

